	/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
	//cout << "Created BTreeIndex" << endl;
    rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	this->mode = mode;
	
	// returns 0 if successfully opened, or -1 if there was an error of some sort
	if(pf.PageFile::open(indexname,mode) != 0)
		return RC_FILE_OPEN_FAILED;

//	cout << "opened page file" << endl;
	
	if(mode == 'w')
		return 0;	// if writing to file, don't need to load data
	
	// this means the mode is 'r'
	else
	{
		char buffer[PageFile::PAGE_SIZE];
		
		if(pf.read(0, buffer) != 0)			// try to read from the file into the buffer
			return RC_FILE_READ_FAILED;
		
		char* p = buffer;
		memcpy(&rootPid, p, sizeof(PageId));
		memcpy(&treeHeight, p + sizeof(PageId), sizeof(int));
		
		
		return 0;	
	}
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    char buffer[PageFile::PAGE_SIZE];
	char* p = buffer;
	if(mode == 'w')
	{
		memset(p, 0, PageFile::PAGE_SIZE);		// zero out the buffer
		memcpy(p, &rootPid, sizeof(PageId));	// write the rootPid to buffer
		memcpy(p + sizeof(PageId), &treeHeight, sizeof(PageId));		// write the treeHeight to buffer
		if(pf.write(0, buffer) != 0)			// write the buffer to the page file
			return RC_FILE_WRITE_FAILED;
	}
	
	return pf.close();	// will return 0 if closed correctly
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	
	// We need to find out where to insert the key, RecordId so we will store that in an IndexCursor.
	IndexCursor cursor;
	BTLeafNode leaf;
	
	locate(key,cursor);		// find where key goes
	 
	// There is only a root node
	if(treeHeight == 1) 
	{
		//cout << "there is only root node right now"  << endl;
		
		leaf.read(cursor.pid, pf);	// read the page id from the page file of where the record should be inserted
		
		
		if(leaf.insert(key, rid) != 0)	// leaf.insert will return non zero if the node is full
		{
			BTLeafNode sibling;
			int siblingKey;
			
			leaf.insertAndSplit(key, rid, sibling, siblingKey);
			
			PageId nextPtr = leaf.getNextNodePtr();
			sibling.setNextNodePtr(nextPtr);		// Set the Pid ptr of the sibling node to where the leaf node originally pointed to
			leaf.setNextNodePtr(pf.endPid());		// The Last Pid is now the sibling node because there are only 2 nodes
			
			if(leaf.write(cursor.pid, pf) != 0)
				return RC_FILE_WRITE_FAILED;
			
			if(sibling.write(pf.endPid(), pf) != 0)
				return RC_FILE_WRITE_FAILED;

			
			BTNonLeafNode root;
			root.initializeRoot(cursor.pid, siblingKey, pf.endPid()-1);		// create root pointing to the nodes just created
			
			if(root.write(pf.endPid(), pf) != 0)		// writing the root Node to the end of the page file
				return RC_FILE_WRITE_FAILED;
		
			rootPid = pf.endPid() - 1;			// the root is now at the end so it has the new Pid
			treeHeight++;						// added a new root so the height increases by 1
			return 0;
		}
		else		// if node is not full, we can just write to it directly
		{
			leaf.write(cursor.pid,pf);
			return 0;
		}
	}
	
	// This means that the tree height is > 1, so there is more than just a root node
	else	
	{
		if(leaf.insert(key, rid) != 0)	// leaf.insert will return non zero if the node is full
		{
			BTLeafNode sibling;
			int siblingKey;
			
			leaf.insertAndSplit(key, rid, sibling, siblingKey);
			
			PageId nextPtr = leaf.getNextNodePtr();
			sibling.setNextNodePtr(nextPtr);		// Set the Pid ptr of the sibling node to where the leaf node originally pointed to
			leaf.setNextNodePtr(pf.endPid());		// The Last Pid is now the sibling node because there are only 2 nodes
			
			if(leaf.write(cursor.pid, pf) != 0)
			{
				return RC_FILE_WRITE_FAILED;
			}
			if(sibling.write(pf.endPid(), pf) != 0)
			{
				return RC_FILE_WRITE_FAILED;
			}
			
			BTNonLeafNode nonLeaf;
			PageId p;
			PageId prevId;
			BTNonLeafNode nonLeafSibling;		// This is a nonleaf sibling node we need to split the parent pageId
			int midKey;							// This is the middle key after the split
			int iteration = 0;
			do {
				prevId = p;
				
				p = pageList.back();		// gets last element in vector (which is parent pageId
				pageList.pop_back();		// removes last element in vector
				
				if(nonLeaf.read(p, pf) != 0)		// read the parent pageId into nonLeaf
					return RC_FILE_READ_FAILED;
				
				if(iteration == 0) 
				{

					if(nonLeaf.insert(siblingKey, pf.endPid()-1) == 0)  // This means that the key was inserted into the parent PageId successfully
					{
						
						if(nonLeaf.write(p, pf) != 0)		// write the new parent node
							return RC_FILE_WRITE_FAILED;
						
						break;
					} 
					// This means that we couldn't successfully insert the key into the parent pageId
					else 
					{
						
						nonLeaf.insertAndSplit(siblingKey, cursor.pid, nonLeafSibling, midKey);
						
						if(nonLeafSibling.write(pf.endPid(), pf) != 0)	// Write the newly created node to the end
							return RC_FILE_WRITE_FAILED;			
						
						if(nonLeaf.write(p, pf) != 0)						// Write the updated non leaf node
							return RC_FILE_WRITE_FAILED;
					}
				} 
				
				// This means we're not on the first iteration, so we need to store the pageId to the parent
				else 
				{
					if(nonLeaf.insert(midKey, prevId) == 0)		// This means that the key was inserted into the parent PageId successfully
					{
						if(nonLeaf.write(p, pf) != 0)
							return RC_FILE_WRITE_FAILED;

						break;
					} 
					else 
					{
						nonLeaf.insertAndSplit(midKey, prevId, nonLeafSibling, midKey);
						if(nonLeafSibling.write(pf.endPid(), pf) != 0)	// Write the newly created node to the end
							return RC_FILE_WRITE_FAILED;
						
						// if at the root page id now, we need to create a new root
						if(p == rootPid)
						{
							BTNonLeafNode root;
							root.initializeRoot(p, midKey, pf.endPid()-1);
							
							if(root.write(pf.endPid(), pf) != 0)		// write the root to the page file
								return RC_FILE_WRITE_FAILED;
						
							rootPid = pf.endPid() - 1;		// the root is assigned the last pageId
							treeHeight++;					// since we added a new root, the height increases
						}
						if(nonLeaf.write(p, pf) != 0)
							return RC_FILE_WRITE_FAILED;
	
						break;
					}
				}
				iteration++;
			} while(p != rootPid);
		}
	}


	// clear the vector
	pageList.clear();
	
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	if(searchKey < 0)
		return -1;		// invalid search key if negative
	
	if(treeHeight == 0)		// means there is no nodes
	{
		rootPid = 1;		// so the rootPid is PageId 1
		cursor.pid = 1;		// the cursor is in the first page
		cursor.eid = 0;		// and it is the first entry
		treeHeight ++;
	}
	else if(treeHeight == 1)	// this means there is just a root node which is a leaf
	{
		BTLeafNode leaf;
		int eid;
		
		// try to read the root PageId from the page file
		if(leaf.read(rootPid, pf) != 0)
			return RC_FILE_READ_FAILED;
		
		if(leaf.locate(searchKey, eid) != 0)
			return RC_NO_SUCH_RECORD;
		
		cursor.pid = rootPid;
		cursor.eid = eid;
	}
	else				// this means that we have to go through the nodes to get the cursor
	{
		BTNonLeafNode b;
		PageId next;
		// if can't read the root node, then return error
		if(b.read(rootPid, pf) != 0)
			return RC_FILE_READ_FAILED;
		
		int depth = 1;	// now at depth 1 since we read the root node
		
		
		// this will traverse down the tree, locating the correct page id where the search key is
		while(depth < treeHeight)
		{
			// the pageList keeps track of page id's traversed to get to the desired one
			if(depth == 1)
				pageList.push_back(rootPid);
			else 
				pageList.push_back(next);
			
			if(b.locateChildPtr(searchKey, next) != 0)
				return RC_NO_SUCH_RECORD;
			
			if(b.read(next, pf) != 0)
				return RC_FILE_READ_FAILED;
			
			depth++;
			
		}
		
		
		/*
		 * Actually do not need htis because the first entry of the leaf node corresponds to key values that are >= to the searchKey so entry 0 will always be >=
		 *
		// once we get to the bottom, we have reached a leaf node so we need to find the eid
		BTLeafNode leafNode;
		int eid;
		
		if(leafNode.read(nextPid, pf) == 0)
		{	
			// locate which entry for the search Key
			if(leafNode.locate(searchKey, eid) != 0)
				return RC_NO_SUCH_RECORD;
		}
		else
		{	// if we can't read the page id where keys are 
			return RC_FILE_READ_FAILED;
		}
		 */
			
		cursor.pid = next;
		cursor.eid = 0;
	}

	
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode b;
		
	if(b.read(cursor.pid, pf) == 0)
	{	
		if(b.readEntry(cursor.eid, key, rid) == 0)
		{
			if (cursor.eid < b.getKeyCount() - 1)	// this means that the cursor is not at the end of the node keys
				cursor.eid++;
			
			// this means that the cursor is at the end of the keys 
			else
			{
				cursor.eid = 0;						// we are going to assign to eid of 0 so it will be the first entry of the next page id
				
				if(b.getNextNodePtr() == 0)		// this means there are no next nodes to read from
					return RC_END_OF_TREE;			// so return we have reached the end
		
				cursor.pid = b.getNextNodePtr();	// this changes the cursor pid to the next pid
			}		
			return 0;
		}
		else
		{
			return -1;		// error if doesn't properly read entry
		}
	}
	else
	{
		return RC_FILE_READ_FAILED;		// if can't properly read, return error code
	}
}
